#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>

using namespace std;
namespace cfy1//暴力超时了
{
    class Solution {
    public:
        bool is_reverse(string s, int begin, int end)
        {
            while (begin <= end)
            {
                if (s[begin++] != s[end--])
                {
                    return false;
                }
            }
            return true;

        }
        string longestPalindrome(string s) {
            vector<string> result;
            int maxlen = 0;
            for (int i = 0; i < s.size(); i++)
            {
                for (int j = i; j < s.size(); j++)
                {
                    if (is_reverse(s, i, j))
                    {
                        string ret = s.substr(i, j-i+1);
                        if (maxlen < ret.size())
                        {
                            maxlen = ret.size();
                        }
                        result.push_back(ret);
                    }
                }
            }
            for (int i = 0; i < result.size(); i++)
            {
                if (result[i].size() == maxlen)
                {
                    return result[i];
                }
            }
            return s;
        }

        void test()
        {
            string s("A");
            string p = longestPalindrome(s);
            cout << p;
        }
    };
}
namespace cfy2
{
    class Solution {
    public://中心扩散法
        string longestPalindrome(string s) {
            int len = s.size();
            if (len == 0 || len == 1)
                return s;
            int start = 0;//记录回文子串起始位置
            int end = 0;//记录回文子串终止位置
            int mlen = 0;//记录最大回文子串的长度
            for (int i = 0; i < len; i++)
            {
                int len1 = expendaroundcenter(s, i, i);//一个元素为中心
                int len2 = expendaroundcenter(s, i, i + 1);//两个元素为中心
                mlen = max(max(len1, len2), mlen);
                if (mlen > end - start + 1)
                {
                    start = i - (mlen - 1) / 2;
                    end = i + mlen / 2;
                }
            }
            return s.substr(start, mlen);
            //该函数的意思是获取从start开始长度为mlen长度的字符串
        }
   // private:
        int expendaroundcenter(string s, int left, int right)
            //计算以left和right为中心的回文串长度
        {
            int L = left;
            int R = right;
            while (L >= 0 && R < s.length() && s[R] == s[L])
            {
                L--;
                R++;
            }
            return R - L - 1;
        }
        void test()
        {
            string s("babcd");
            string p = longestPalindrome(s);
            cout << p;
        }
    };

    
}

int main()
{
    cfy2::Solution A;
    A.test();
    return 0;
}